To address the problems of high global query sensitivity and low utility of mining results in the existing works, a Lattice-Trajectory Pattern Mining (LTPM) algorithm based on prefix sequence lattice and trajectory truncation was proposed for mining sequential patterns with differential privacy. An adaptive method was employed to obtain the optimal truncation length, and a dynamic programming strategy was used to truncate the original database. Based on the truncated database, the equivalent relation was used to construct the prefix sequence lattice for mining trajectory patterns. Theoretical analysis shows that LTPM satisfies ε-differential privacy. The experimental results show that the True Postive Rate (TPR) and Average Relative Error (ARE) of LTPM are better than those of N-gram and Prefix algorithms, which verifies that LTPM can effectively improve the utility of the mining results.